#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_
#include <cstddef>
#include "LinkQueue.h"

using ElementType = void*;
class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();

    void Insert(const ElementType& element); //数据插入
    
    void show();

    ElementType* FindElement(const ElementType& element);

    void RemoveByElement(const ElementType& element);

    void NodeNum();
private:
    struct TreeNode //树中节点
    {
        TreeNode (const ElementType& element)
        {
            value = element;
            left = right = parent = nullptr;
        }
        ElementType value; //数据
        TreeNode * left; //左孩子
        TreeNode * right; //右孩子
        TreeNode * parent; //双亲
    };

    TreeNode* InsertNode(TreeNode* node,const ElementType& element);

    void PrevTravel(TreeNode* node);

    void MidTravel(TreeNode* node);

    void PostTravel(TreeNode* node);

    void FreeNode(TreeNode* node);

    TreeNode* RemoveNode(TreeNode* node,const ElementType& element);

    ElementType* FindNode(TreeNode* node,const ElementType& element);

    TreeNode* GetMinNode(TreeNode* node); //获取一个树的最小值点

    TreeNode* RotateRight(TreeNode* node);//右旋

    TreeNode* RotateLeft(TreeNode* node);//左旋

    TreeNode* RotateLeftRight(TreeNode* node);//左右旋

    TreeNode* RotateRightLeft(TreeNode *node);//右左旋

    int GetNodeHigh(TreeNode * node);//获取树高

    int LeftRightDev(TreeNode* node);//左右子树高度差

    TreeNode * root; //根节点

    bool IsComplete(TreeNode* node);

    void OrderTravel(TreeNode *node); //层序遍历

    void NodeNum(TreeNode * node,int &Onedu,int &Towdu);

};


#endif